package one.queue;

/**
 * 双端队列：（循环双端队列）
 * 思路：
 * 1）使用双链表实现
 * 2）队空：tail=head；队满：size=capacity
 */
public class Deque {
    private Node head;
    private Node tail;
    private int capacity;
    private int size;
    public Deque(){
        this.head = null;
        this.tail = null;
        this.capacity = 10;
        this.size = 0;
    }
    public Deque(int capacity){
        this();
        this.capacity = capacity;
    }

    public boolean isEmpty(){
        return size == 0; //head == tail
    }
    public boolean isFull(){
        return size == capacity;
    }
    public boolean insertLast(int val){
        if(isFull()){
            return false;
        }
        if(tail == null){
            tail = new Node(val);
            head = tail;
        }else {
            Node node = new Node(val);
            tail.next = node;
            node.pre = tail;
            tail = node;
        }
        size++;
        return true;
    }
    public boolean insertFront(int val){
        if(isFull()){
            return false;
        }
        if(head == null){
            head = new Node(val);
            tail = head;
        }else {
            Node node = new Node(val);
            node.next = head;
            head.pre = node;
            head = node;
        }
        size++;
        return true;
    }
    public boolean deleteLast(){
        if(isEmpty()){
            return false;
        }
        if(size == 1){
            head = null;
            tail = null;
            size--;
            return true;
        }
        Node node = tail.pre;
        node.next = null;
        tail = node;
        size--;
        return true;
    }
    public boolean deleteFront(){
        if(isEmpty()){
            return false;
        }
        if(size == 1){
            head = null;
            tail = null;
            size--;
            return true;
        }
        Node node = head.next;
        node.pre = null;
        head = node;
        size--;
        return true;
    }
    public int getRear(){
        if(isEmpty()){
            return -1;
        }
        return tail.val;
    }
    public int getFront(){
        if(isEmpty()){
            return -1;
        }
        return head.val;
    }
}
class Node{
    int val;
    Node pre;
    Node next;
    public Node(){}
    public Node(int val){
        this.val = val;
    }
}
